a = [1, 7, 0, 10, 9, 5]
# 冒泡排序算法
# def bubbleSort(arr):
#     if arr == None or  len(arr) < 2 :
#         return
#     for e in range(len(arr) -1):
#         for i in range(len(arr) -1- e):
#             if arr[i] > arr[i +1]:
#                 swap(arr,i,i+1)
#     return arr
# print(bubbleSort(a))


# 直接插入排序
# def insert_sort(array):
#     for i in range(len(array)):
#         for j in range(i):
#             if array[i] < array[j]:
#                 array.insert(j,array.pop(i))
#                 break
#     return array
# print(insert_sort(a))


# 希尔排序
# def shell_sort(array):
#     gap = len(array)
#     while gap > 1:
#         gap = gap // 2
#         for i in range(gap, len(array)):
#             for j in range(i % gap, i, gap):
#                 if array[i] < array[j]:
#                     array[i], array[j] = array[j], array[i]
#     return array
# print(shell_sort(a))


# 简单选择排序

# def select_sort(array):
#     for i in range(len(array)):
#         x = i  # min index
#         for j in range(i, len(array)):
#             if array[j] < array[x]:
#                 x = j
#         array[i], array[x] = array[x], array[i]
#     return array
# print(select_sort(a))

# 堆排序
def heapSort(arr):
    if arr == None or len(arr)<2:
        return
    # 形成一个大根堆 但是不是有序
    for i in range(len(arr)):
        heapinsert(arr,i)
    size = len(arr) -1
    swap(arr,0,size)
    while size>0:
        heapify(arr,0,size)
        size -= 1
        swap(arr,0,size)
        print(arr)
    return arr

def heapify(arr,index,size):
    left = index * 2+1
    while left<size:
        if left+1<size and arr[left]<arr[left+1]:
            largr =  left+1
        else:
            largr = left
        if arr[index] > arr[largr]:
            largr = index
        else:
            largr = largr
        if largr == index:
            break
        swap(arr,largr,index)
        index =  largr
        left = 2*index+1
def heapinsert(arr,index):
    while arr[index] >arr[int((index-1)/2)]:
        swap(arr, index, int((index - 1) / 2))
        index = int((index-1)/2)

def swap(arr,i,j):
    tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
print(heapSort(a))


# 快速排序

def quick_sort(array):
    def recursive(begin, end):
        if begin > end:
            return
        l, r = begin, end
        pivot = array[l]
        while l < r:
            while l < r and array[r] > pivot:
                r -= 1
            while l < r and array[l] <= pivot:
                l += 1
            array[l], array[r] = array[r], array[l]
        array[l], array[begin] = pivot, array[l]
        recursive(begin, l - 1)
        recursive(r + 1, end)

    recursive(0, len(array) - 1)
    return array

# print(quick_sort(a))



#归并排序

# def merge_sort(array):
#     def merge_arr(arr_l, arr_r):
#         array = []
#         while len(arr_l) and len(arr_r):
#             if arr_l[0] <= arr_r[0]:
#                 array.append(arr_l.pop(0))
#             elif arr_l[0] > arr_r[0]:
#                 array.append(arr_r.pop(0))
#         if len(arr_l) != 0:
#             array += arr_l
#         elif len(arr_r) != 0:
#             array += arr_r
#         return array
#
#     def recursive(array):
#         if len(array) == 1:
#             return array
#         mid = len(array) // 2
#         arr_l = recursive(array[:mid])
#         arr_r = recursive(array[mid:])
#         return merge_arr(arr_l, arr_r)
#
#     return recursive(array)
#
# print(merge_sort(a))